package com.hainiu.cat.sort.write;

import com.hainiu.cat.util.SortUtil;

/**
 * create by biji.zhao on 2021/5/30
 * 堆排序
 *       0
 *   1      2
 * 3  4    5  6
 *
 * 这里以最大堆为列
 */
public class HeapSort {

    private int[] data;

    public void addOne(int e) {
        // 添加到尾部
        data =  addToLast(e);
        shiftUp(data.length - 1);
    }

    public int removeOne() {
        int pop = data[0];
        // 头尾交换
        SortUtil.swap(data, 0, data.length - 1);
        // 移除最后一个
        data = removeLast(data);
        // 下沉
        shiftDown(0);
        return pop;
    }

    // 获取父节点
    private static int getParent(int curr) {
        return (curr - 1) / 2;
    }
    // 获取左子节点
    private static int getLeftChild(int curr) {
        return (curr * 2) + 1;
    }
    // 获取右子节点
    private static int getRightChild(int curr) {
        return (curr * 2) + 2;
    }
    // 上浮
    private void shiftUp(int k) {
        while (getParent(k) >= 0 && data[getParent(k)] > data[k]) {
            SortUtil.swap(data, k, getParent(k));
            // 油表往上
            k = getParent(k);
        }

    }
    // 下沉
    private void shiftDown(int k) {
        while (getLeftChild(k) < data.length) {
            int l = getLeftChild(k);
            int r = getRightChild(k);
            if (r < data.length && data[r] < data[l]) {
                l = r;
            }
            if (data[l] < data[k]) {
                SortUtil.swap(data, k, l);
            }
            k = l;
        }
    }
    // 删除最后一个节点
    private static int[] removeLast(int[] array) {
        if (array.length == 0 || array.length == 1) {
            return array;
        }
        int[] newArray = new int[array.length - 1];
        System.arraycopy(array, 0, newArray, 0, array.length - 1);
        return newArray;
    }
    // 尾部添加一个元素
    private int[] addToLast(int e) {
        int[] newArray = new int[data.length + 1];
        System.arraycopy(data, 0, newArray, 0, data.length);
        newArray[data.length] = e;
        return newArray;
    }

    public static void main(String[] args) {
        int [] assays = {101, 20, 3, 51, 7, 30, 47, 58, 100};
        SortUtil.arrayToString(assays);

        HeapSort heapSort = new HeapSort();
        heapSort.data = new int[]{};
        for (int i = 0; i < assays.length; i++) {
            heapSort.addOne(assays[i]);
        }

        int[] newArray = new int[assays.length];
        for (int i = 0; i < assays.length; i++) {
            newArray[i] = heapSort.removeOne();
        }
        SortUtil.arrayToString(newArray);
    }

}
